0

I'm just learning all the basic stuff about Stack in my Data Structure C++ class. However, it's getting a bit confused between them. Can anyone tell me whats the def. of arrayStack and arrayQueue, stackQueue and their differences ? and the text book is not really helpful at all.

Hoang Minh
  • 1,066
  • 2
  • 21
  • 40

5 Answers5

4
Firstly you need to understand the fundamentals, lets take a ride thorough the basics again.

We begin with stack empty:

-----
stack
Now, let's perform Push(stack, A), giving:

-----
| A |  <-- top
-----
stack
Again, another push operation, Push(stack, B), giving:

-----
| B |  <-- top
-----
| A |
-----
stack

Stacks

The conceptual picture of a stack is something like this:

Now let's remove an item, letter = Pop(stack), giving:

-----              -----
| A |  <-- top     | B |
-----              -----
stack              letter
And finally, one more addition, Push(stack, C), giving:

-----
| C |  <-- top
-----
| A |
-----
stack
You'll notice that the stack enforces a certain order to the use of its contents, i.e., the Last thing In is the First thing Out. Thus,

we say that a stack enforces LIFO order.

Now we can see one of the uses of a stack...To reverse the order of a set of objects.


Like a stack, a queue usually holds things of the same type. We usually draw queues horizontally. Here's a queue of characters with 3

elements:

queue
-------------
| a | b | c |
-------------
  ^       ^
  |       |
front    rear


Queues are useful because they produce a certain order in which the contents of the queue are used. Let's see what order that is by

looking at a queue of characters. Now, what would a particular sequence of Enter and Deletes do to this queue:

queue
-------------
| a | b | c |
-------------
  ^       ^
  |       |
front    rear
Now, Enter(queue, 'd')...

queue
-----------------
| a | b | c | d |
-----------------
  ^           ^
  |           |
front        rear
Now, ch = Delete(queue)...

queue           ch
-------------   -----
| b | c | d |   | a |
-------------   -----
  ^       ^
  |       |
front    rear
kotAPI
  • 1,073
  • 2
  • 13
  • 37
  • Thanks kotAPI. What is about Array Stack and Array Queue, and Stack Queue data structure ? are they array or stack or queue ? http://opendatastructures.org/ods-cpp.pdf – Hoang Minh Sep 25 '13 at 09:41
  • Array stack- implementing stack using arrays in programming. Array Queue- implementing queue using arrays in programming. – kotAPI Sep 25 '13 at 09:47
  • @kotAPI, It looks like you have quoted this answer from another answer. It would be nice if you mention where you copied this from. – Shahbaz Sep 25 '13 at 12:00
1

Both the stack and the queue are data structures that grow naturally as you add elements.

  • In a stack, elements are added (pushed) to the one side of the stack and then retrieved (popped) from the same side of the stack. In other words, the last element you insert is the first element you can retrieve. This type of data structure is known as LIFO (Last In, First Out).
  • In a queue, elements are added to the back of the queue and retrieved from the front. In other words, the first element you insert is the first element you can retrieve. This type is known as FIFO (First In, First Out).

In various languages (not specifically C++ or its libraries), there are various ways that naturally growing data structures can be implemented. One such way is by keeping a simple internal array: Elements are stored in the array and the add/remove operations take care of growing or shrinking that internal array, without bothering you. Usually, when a structure is called ArraySomething, it should mean something along these lines.

Theodoros Chatzigiannakis
  • 28,773
  • 8
  • 68
  • 104
1

An ArrayStack is intern based on an array.

The most important difference of them all is, that a Stack is based on the LIFO (Last In First Out) system, so you add your elements to the top (push) and if you want to take an element form the stack (pop), you also take it from the top. If you add a few elements:

stack.push(1), stack.push(2), stack.push(3)

and then pop one off:

stack.pop() //returns 3

A Queue is based on the FIFO (First In First Out) system, so you add elements on the "back" of the queue and you get your elements from the "front" of the queue. This means if you add three elements:

queue.add(1), queue.add(2), queue.add(3)

and then want to get an element from the queue:

queue.get() //returns 1

ArrayStack, ArrayQueue means, that they are implemented as an array. And a StackQueue is a combination of both. You could get your elements from the front and from the back.

Alex VII
  • 930
  • 6
  • 25
  • I have never heard of an ArrayStack before. Is this a guess, or have you read the same book? – doctorlove Sep 25 '13 at 09:31
  • This just means, that the implementation behind the stack or the queue is an array, not a linked list or something like that. – Alex VII Sep 25 '13 at 09:35
  • so if it is an ArrayStack, it still has to follow the rule LIFO, and if it is a ArrayQueue, it based on the FIFO ? – Hoang Minh Sep 25 '13 at 09:46
  • Yes, so this could be a class, that uses an array to store its data, but only allows you to to input and get your data following the FIFO or LIFO rules. – Alex VII Sep 25 '13 at 10:03
1

An array is a way to organize data (and its storage allocations), whereas stack and queue are policies to insert, remove or access data.

Different policies can be combined with the organizations to construct different data structures according to your needs.

For example:

  • Stack using an array
  • Queue using an array
  • Stack using a linked list
  • Tree using an array etc.
HAL
  • 3,888
  • 3
  • 19
  • 28
0

C++ Standard doesn't say anything about the structures you've mentioned (apart from std::stack container adapter). Hence, you have to read the chapter again.

Most probably you can also throw the book away, too, and start using standard containers instead.

Bartek Banachewicz
  • 38,596
  • 7
  • 91
  • 135