Can I use a singly linked list for stacks and queues?
Author
Hello,
I've been studying my favorite data structure, the linked list, for the past few weeks and I was wondering, after reading an article on stacks and queues, if its possible to just use a singly list for both stacks and queues. From reading various articles on the two data structures a singly list seems logical to me with slight modifications of course. The insertion order would be straight forward. Whenever I push a new element I would just be appending the element to the end of the list. In the stack the tail could be the top. In a queue whenever I add new items I would just prepend the list since queues are of FIFO structure. I seriously see nothing wrong with this. Do you?
[Edited by - Khaosifix on January 6, 2005 1:07:30 AM]
No problem with this. In fact, I would say a singly linked list is one of the most common implementations of both of these data structures....
Where did you get the idea that this was unaccepted?
Where did you get the idea that this was unaccepted?
Author
In Ron Penton's book he used an array which makes absolutely no sense to me. Actually he had two implementations. One is a doubly list while the other was an array of stacks. Both methods seem illogical to me since doubly list take up more memory on the pointer table than a singly list.
[Edited by - Khaosifix on January 6, 2005 1:48:31 AM]
[Edited by - Khaosifix on January 6, 2005 1:48:31 AM]
It's fine for a queue. For a stack, you'd want a doubly-linked list. Many times people use a queue they actually want a priority queue, which is better implemented as heap with a tree structure.
Of course you CAN use a singly-linked list for a stack... but think what happens when you pop: you need to set the node before the last to have a 'next' pointer of NULL, but you can't traverse backwards, so you have to traverse the entire list to find "next-to-last".
Of course you CAN use a singly-linked list for a stack... but think what happens when you pop: you need to set the node before the last to have a 'next' pointer of NULL, but you can't traverse backwards, so you have to traverse the entire list to find "next-to-last".
ajas95,
I think you got it a little mixed up. For a stack a singly link list will work great. Since you are pushing and popping off of the same side of the list. However, in a queue it is a little more tricky since you need to pop off of one side and then push on two the other.
I think you got it a little mixed up. For a stack a singly link list will work great. Since you are pushing and popping off of the same side of the list. However, in a queue it is a little more tricky since you need to pop off of one side and then push on two the other.
Nah, he's right. A slist stack would grow well, but not shrink.
OP: You like lists? Nobody likes lists! ;)
OP: You like lists? Nobody likes lists! ;)
This stack with a slinked list grows and shrinks in constant time.
#include
#include
using namespace std;
template
struct Cell
{
public:
Cell(T t, Cell *lst)
{
item = t;
next = lst;
}
T item;
Cell *next;
};
template
class Stack
{
public:
Stack( T emptyValue ) { head = NULL; this->emptyValue = emptyValue; }
void push(T t)
{
Cell *h = new Cell(t, head);
head = h;
}
T pop()
{
if (head == NULL) return this->emptyValue;
Cell *ptr = head;
T t = head->item;
head = head->next;
delete ptr;
return t;
}
void display()
{
if ( empty() ) { cout next) cout item) *s = new Stack( -1 );
s->display();
s->push(1);
s->display();
s->push(2);
s->display();
s->push(3);
s->display();
s->push(4);
s->display();
s->pop();
s->display();
s->pop();
s->display();
s->pop();
s->display();
s->pop();
s->display();
system("PAUSE");
return 0;
}
-The code is a little sloppy
#include
#include
using namespace std;
template
struct Cell
{
public:
Cell(T t, Cell *lst)
{
item = t;
next = lst;
}
T item;
Cell *next;
};
template
class Stack
{
public:
Stack( T emptyValue ) { head = NULL; this->emptyValue = emptyValue; }
void push(T t)
{
Cell *h = new Cell(t, head);
head = h;
}
T pop()
{
if (head == NULL) return this->emptyValue;
Cell *ptr = head;
T t = head->item;
head = head->next;
delete ptr;
return t;
}
void display()
{
if ( empty() ) { cout next) cout item) *s = new Stack( -1 );
s->display();
s->push(1);
s->display();
s->push(2);
s->display();
s->push(3);
s->display();
s->push(4);
s->display();
s->pop();
s->display();
s->pop();
s->display();
s->pop();
s->display();
s->pop();
s->display();
system("PAUSE");
return 0;
}
-The code is a little sloppy
Quote:Original post by ajas95Sorry but, Bollucks!
It's fine for a queue. For a stack, you'd want a doubly-linked list. Many times people use a queue they actually want a priority queue, which is better implemented as heap with a tree structure.
Of course you CAN use a singly-linked list for a stack... but think what happens when you pop: you need to set the node before the last to have a 'next' pointer of NULL, but you can't traverse backwards, so you have to traverse the entire list to find "next-to-last".
Khaosifix and SnprBoB86 had it absolutely correct straight off.
A singly-linked-list is perfect for both a stack and a queue (the two main uses).
With a stack you add and remove from the head. They are O(1) operations known as 'Push' and 'Pop'.
With a queue you add at the tail and remove from the head. They are O(1) operations known as 'Put' and 'Get'.
There is absolutely no reason whatsoever to use a doubly-linked-list. Doing so would be ridiculous and actually make it far LESS efficient!
This is pretty basic stuff that I'd expect most programmers to know.
You guys must have a serious caffiene deficiency today or something.[smile]
Are you going to slap yourselves on the forehead now, or do I have to post code first?
Quote:Original post by Anonymous Poster
ajas95,
I think you got it a little mixed up.
Right, my thinking was skewed by the OP :)
For a stack if you push on to the front of a linked list it's no problem. However, I still maintain that a queue is also easy to represent with a singly-linked list... you just need to store one pointer to the last element in the list no know where to insert.
So, to the OP: Both are fine, except do your insertion the opposite way you describe.
[edit]
And to iMalc, while I respect your "There is absolutely no reason whatsoever to use a doubly-linked-list. Doing so would be ridiculous and actually make it far LESS efficient!"...
write me a swap(A, B) implementation for a singly-linked list... that works in ALL cases (where A and B are valid).
[/edit]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
