What is a stack and a queue?

ID:152986
 
Apr 26 2005, 10:23 pm (Edited by moderator on Apr 26 2005, 11:08 pm)
I wish there were computer science classes at my school so I could learn what a stack and a queue is!

Is a queue sort of a list of actions that require sequential access, and a stack more like a tree? (With the trunk at the top, of course. Obviously programmers never go outside and lok at trees. :P)
Apr 26 2005, 11:01 pm
Is a queue sort of a list of actions that require sequential access, and a stack more like a tree? (With the trunk at the top, of course. Obviously programmers never go outside and lok at trees. :P)

They are actually quite simple.

A stack is a simple data structure with two methods push and pop. Whenever you push something onto a stack you put it at the top of the stack. Then when you do a pop you take the top item off the stack. Here's a simple implementation of one.

Stack
  var/L[]
  New()
    L = new()
  proc/Push(d)
    L.Add(d)
  proc/Pop()
    ASSERT(L.len)
    . = L[L.len]
    L.Cut(L.len)
  proc/IsEmpty()
    return L.len > 0


A queue works similiarly. Except when you remove an item you take out the oldest item rather than the newest. Which I guess is like how you described it. It pretty much works like a line where the people who are first in line get through it first.

Queue
  var/L[]
  New()
    L = new()
  proc/Enqueue(d)
    L.Add(d)
  proc/Dequeue()
    ASSERT(L.len)
    . = L[1]
    L.Cut(1,1)
  proc/IsEmpty()
    return L.len > 0


A tree is a recurive data structure since at each branch can have any number of children each of which can have their own children, etc. There are many many kinds of tree data structures.

Also while I used lists for the implemenations shown here you can also used linked lists which would probably be better for a queue if you are concerned about effeciency. Because if lists are internally done with arrays then removing an item from the begining of a list requires moving all the items in front of it back one place to maintain shape. For larger lists this could be time consuming. With a linked list you can keep a pointer to the head and tail and enqueue and dequeue with constant time regardless of list size. An since random access isn't needed for a queue there isn't any real disadvantage to using a linked list.
Apr 26 2005, 11:43 pm
In response to Theodis
I also happen to not know what linked lists are. Nor pointers. I've never gone into any C, and that's the context I keep hearing/reading that term in. 'Cause, I'm not hugely old either. But if I point that out, Crispy comes in and makes me cry by pointing out that he's done a lot more in a simnilar timeframe. :P

It's probably really annoying getting all these questions about data types, hmm? Still, I'm learning a hell of a lot from BYOND, due to these sorts of things. When I finally do some computer science, I'll probably do pretty well.
Apr 27 2005, 1:07 am
In response to Jp
I also happen to not know what linked lists are. Nor pointers.

A pointer is a simple concept of having a variable store the address of another :P.

Anyway a linked list is a list but rather than allocating a chunk of memory like you would with an array you just build it one item at a time. Each item has a reference/pointer to the next item in the list and the last one points to null(so you know it is the end).

A basic implementation of one is

LinkedListNode
  var/data
  var/LinkedListNode/next
  New(d)
    data = d
    next = null
  proc/Count
    . = 0;
    for(var/LinkedListNode/i = src; i.next; i = i.next)
      .++;
  proc/Add(d)
    var/LinkedListNode/i = src
    //Find the last node in the list
    while(i.next)
      i = i.next
    //Add in the new node
    i.next = new(d)
    return i.next


Then to use one simply make a head node(and in this case it should have data. Here's an example.

proc/SomeProc()
  var/LinkedListNode/head = new(0)
  //Fill up the linked list with the numbers 0 to 9.
  for(int i = 1; i < 10; i++)
    head.Add(i)
  //Output them
  for(var/LinkedListNode/i = head; i.next; i = i.next)
    world << i.data


This is the basic idea of how to make and use one. I didn't include a remove proc because removing items is slightly tricky and I wouldn't want to try and get it right off the top off my head without testing.

Though in DM you probably will never use a linked list unless it is part of a different data structure like a tree or a queue since most of its bonuses really don't apply though the downsides do. The main bonuses of linked lists is that it is dynamic in size(with an array you have to create a new one and copy over the old contents to adjust size) and you don't need to allocate a contiguous chunk of memory(in C if you allocate a large array all the memory has to be in one large block or you'll get an error when trying to make a new array even if you have lots of free fragmented memory). Of course the fact that you are allocating memory in arbitrary locations is the type of thing that leads to memory fragmentation quickly. The downside to a linked list is that you no longer have random access so if you want to get to the fifth element in the list you have to go through all the nodes before it to get to it. In my example this applies when adding an item(and removing if I added it) along with counting size.

Though as I noted for a queue this isn't really a problem as you can keep a reference to the head and tail and since you aren't supposed to iterate througha queue random access isn't an issue. Removing the head is quite trivial just do
head = head.next and boom now the head item is the second one in the list and you didn't have to move any of the other nodes to maitain the structure of the list. To add an item you simply do tail = tail.Add(newitem) and you add in an item without iterating through the list.

And now since I've went through the process of writing the LinkedList code here is a Queue using one :P.
Queue
  var/LinkedListNode/head
  var/LinkedListNode/tail

  New()
    head = null
    tail = null
  proc/Enqueue(d)
    if(!tail)
      //If there is no tail but a head something got corrupted
      ASSERT(!head)
      if(!head)
        head = new(d)
        tail = head
    else
      tail = tail.Add(d)
  proc/Dequeue()
    ASSERT(head)
    . = head.data
    head = head.next
    //If there is no head ensure there is no tail either
    if(!head)
      tail = null
  proc/IsEmpty()
    return head != null

LinkedListNode
  var/data
  var/LinkedListNode/next
  New(d)
    data = d
    next = null
  proc/Count
    . = 0;
    for(var/LinkedListNode/i = src; i.next; i = i.next)
      .++;
  proc/Add(d)
    var/LinkedListNode/i = src
    //Find the last node in the list
    while(i.next)
      i = i.next
    //Add in the new node
    i.next = new(d)
    return i.next


Maybe once my finals week is over I should find some time to write some tutorials on this type of stuff :P.
Apr 27 2005, 11:04 am
In response to Jp
You know, I've been thinking recently that an upcoming Dream Tutor article should be on basic data structures. BYOND programmers could certainly use some of that info.

Lummox JR