3.4. The Stack Abstract Data Type

The stack abstract data type is defined by the following structure and operations. A stack is structured, as described above, as an ordered collection of items where items are added to and removed from the end called the “top.” Stacks are ordered LIFO. The stack operations are given below.

For example, if s is a stack that has been created and starts out empty, then Table 1 shows the results of a sequence of stack operations. Under stack contents, the top item is listed at the far right.

Table 1: Sample Stack Operations
Stack Operation Stack Contents Return Value
s.empty() [] 1
s.push('horse') ['horse']  
s.push('dog') ['horse','dog']  
s.top() ['horse','dog'] 'dog'
s.push('cat') ['horse','dog','cat']  
s.size() ['horse','dog','cat'] 3
s.empty() ['horse','dog','cat'] 0
s.push('turtle') ['horse','dog','cat','turtle']  
s.pop() ['horse','dog','cat']  
s.pop() ['horse','dog']  
s.size() ['horse','dog'] 2
    Q-1: Which group of data would not make a valid Stack?
  • 's', 't', 'a', 'c', 'k', 's'
  • No, this is valid for a stack. Check the reading for what types of data a stack can have.
  • "Stacks"
  • No, a stack can have only one item.
  • 115, 116, 97, 99, 107
  • No, this is valid for a stack similar to A. Check the reading.
  • "St", 'a', "ck", 's'
  • Yes, stacks should have data of the same type.
Next Section - 3.5. Using a Stack in C++