stack

Source: http://www.cplusplus.com/reference/stl/stack/

LIFO stack
Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from the end of the container.

stacks are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements arepushed/popped from the "back" of the specific container, which is known as the top of the stack.

The underlying container may be any of the standard container class templates or some other specifically designed container class. The only requirement is that it supports the following operations:

back()
push_back()
pop_back()

Therefore, the standard container class templates vector, deque and list can be used. By default, if no container class is specified for a particular stack class, the standard container class template deque is used.

In their implementation in the C++ Standard Template Library, stacks take two template parameters:

template < class T, class Container = deque<T> > class stack;

Where the template parameters have the following meanings:

T: Type of the elements.
Container: Type of the underlying container object used to store and access the elements.

In the reference for the stack member functions, these same names are assumed for the template parameters.

Member functions

(constructor)

Construct stack (public member function)

empty

Test whether container is empty (public member function)

size

Return size (public member function)

top

Access next element (public member function)

push

Add element (public member function)

pop

Remove element (public member function)

//Stacks in c++

//This would be example of a stack of integers using a list....

//php

//example of a stack ( Last in First out = LIFO) using a list

// DEV C++

// http://www.daniweb.com/software-development/cpp/threads/18764

#include<iostream>

#include<list>

using namespace std;

int main()

{

list<int> iL;

int k;

//load the stack with numbers 0 to 9, last number entered would be on top

for( k= 0; k< 9; k++)

iL.push_front(k);

//now unload the stack and display

cout<<"Unload the stacks in order.\n";

for( k =0; k<10;k++)

{

//read the top element of the list.

cout<< iL.front() << endl;

cin.get(); // wait

// now pot it ( removes the top element)

iL.pop_front();

}

return 0;

}

//[/php]

**************************************************************
************************************************************

http://www.fredosaurus.com/notes-cpp/datastructs/ex1/usingstack.html

One of three contrasting examples of solving the problem with increasingly powerful tools: using arrays, thenvectors, then stacks.

// Read words and print them in reverse order.
//   Variation using stack and string.
// Fred Swartz 2001-11-08, 2001-12-04

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {

    stack<string> allwords; // stack of all words
    string word;            // input buffer for words.

    // read words/tokens from input stream
    do
  {
          cin>> word;
          if ( word == "0") break;
          allwords.push(word);
          
}while ( 1);
    
    
    cout << "Number of words = " << allwords.size() << endl;

    // write out all the words in reverse order.
    while (!allwords.empty()) {
       cout << allwords.top() << endl;
       allwords.pop();            // remove top element
    }
    return 0;
}//end main

*************************************************************

source: http://theonlinetutorials.com/c-program-to-implement-stack-using-linked-list.html



#include <iostream.h>
template<class T>
class Node
{
	friend LinkedStack<T>;
	private:
	T data;
	Node<T> *link;
};
template<class T>
class LinkedStack {
	public:
		LinkedStack() {top = 0;}
		~LinkedStack();
		int IsEmpty() const {return top == 0;}
		T Top() const;
		LinkedStack<T>& Add(const T& x);
		LinkedStack<T>& Delete(T& x);
	private:
		Node<T> *top;
};
	template<class T>
LinkedStack<T>::~LinkedStack()
{// Stack destructor..
	Node<T> *next;
	while (top) {
		next = top->link;
		delete top;
		top = next;
	}
}
template<class T>
T LinkedStack<T>::Top() const
{// Return top element.
	if (IsEmpty()) cout<<"Stack empty:";
	else
		return top->data;
}
	template<class T>
LinkedStack<T>& LinkedStack<T>::Add(const T& x)
{// Add x to stack.
	Node<T> *p = new Node<T>;
	p->data = x;
	p->link = top;
	top = p;
	return *this;
}
	template<class T>
LinkedStack<T>& LinkedStack<T>::Delete(T& x)
{// Delete top element and put it in x.
	if (IsEmpty())
	{
		cout<<"Stack empty";
		return *this;
	}
	x = top->data;
	Node<T> *p = top;
	top = top->link;
	delete p;
	return *this;
}
void main(void)
{
	int x;
	LinkedStack<int> S;
	S.Add(1).Add(2).Add(3).Add(4);
	cout << "Stack should be 1234" << endl;
	cout << "Stack top is " << S.Top() << endl;
	S.Delete(x);
	cout << "Deleted " << x << endl;
	S.Delete(x);
	cout << "Deleted " << x << endl;
	S.Delete(x);
	cout << "Deleted " << x << endl;
	S.Delete(x);
	cout << "Deleted " << x << endl;
}

source: http://www.cplusplus.com/reference/stl/stack/stack/

stack::stack

public member function

explicit stack ( const Container& ctnr = Container() );

Construct stack
Constructs a stack container adaptor object.
A container adaptor keeps a container object as data. This container object is a copy of the argument passed to the constructor, if any, otherwise it is an empty container.

Parameters

ctnr: Container object
Container is the second class template parameter (the type of the underlying container for the stack; by default:deque<T>, see class description).

Example

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// constructing stacks
#include <iostream>
#include <vector>
#include <deque>
#include <stack>
using namespace std;

int main ()
{
  deque<int> mydeque (3,100);     // deque with 3 elements
  vector<int> myvector (2,200);   // vector with 2 elements

  stack<int> first;               // empty stack
  stack<int> second (mydeque);    // stack initialized to copy of deque

  stack<int,vector<int> > third;  // empty stack using vector
  stack<int,vector<int> > fourth (myvector);

  cout << "size of first: " << (int) first.size() << endl;
  cout << "size of second: " << (int) second.size() << endl;
  cout << "size of third: " << (int) third.size() << endl;
  cout << "size of fourth: " << (int) fourth.size() << endl;

  return 0;
}

Output:

size of first: 0
size of second: 3
size of third: 0
size of fourth: 2

Complexity

Constant (one container construction). Although notice that the container construction itself may not take constant time.

***********************************************************************